/*
https://leetcode-cn.com/problems/race-car/solution/sai-che-by-leetcode/
 */
import java.util.Arrays;

public class Solution818 {
    public int racecar(int target) {
        int[] f=new int[target+3];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0]=0;
        f[1]=1;
        f[2]=4;
        for (int i=3;i<=target;i++){
            int k=32-Integer.numberOfLeadingZeros(i);
            if (i==(1<<k)-1){
                f[i]=k;
            }else{
                for (int j=0;j<k-1;j++){
                    f[i]=Math.min(f[i],f[i-(1<<(k-1))+(1<<j)]+k+j+1);
                }
                f[i]=Math.min(f[i],f[(1<<k)-i-1]+k+1);
            }
        }
        return f[target];
    }

    public static void main(String[] args) {
        System.out.println(new Solution818().racecar(5));
    }
}
